497. Лентяй

Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает “хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

Вход. Первая строка содержит количество тестов. Каждый тест состоит из количества предметов n (1 ≤ n ≤ 100), которые нужно сдать Валере. Далее идут n строк, каждая из которых состоит из двух чисел a и b (1 ≤ a ≤ b ≤ 31), задающих интервал работы очередного преподавателя.

Выход. Для каждого теста выведите в отдельной строке “YES”, если можно встретить всех преподавателей в один день, и “NO” если это невозможно.

Пример входа	Пример выхода
2 4 1 7 4 5 3 8 5 10 2 1 2 3 4	YES NO

РЕШЕНИЕ

циклы

Анализ алгоритма

Пусть x – день, в который Валера сможет сдать все долги. Пусть [a_i, b_i] (1 ≤ i ≤ n) – интервалы работы преподавателей. Тогда очевидно что должно выполняться

max(a₁, …, a_n) ≤ x ≤ min(b₁, …, b_n)

Если max(a₁, …, a_n) ≤ min(b₁, …, b_n), то требуемый день x существует, выводим “YES”. Иначе выводим “NO”.

Пример

Рассмотрим первый тест.

Вычисляем максимум левых концов и минимум правых:

· min = max(1, 4, 3, 5) = 5;

· max = min(7, 5, 8, 10) = 5;

Поскольку min ≤ max (5 ≤ 5), то существует день, когда Валера сможет сдать все долги. Таким днем будет x = 5.

Реализация алгоритма

Читаем количество тестов tests.

scanf("%d", &tests);

Последовательно обрабатываем тесты.

while (tests--)

{

Для каждого теста читаем количество предметов n.

scanf("%d", &n);

Читаем n интервалов [a; b]. Вычисляем

· min = max(a₁, …, a_n),

· max = min(b₁, …, b_n)

min = 0; max = 32;

for (i = 0; i < n; i++)

{

scanf("%d %d", &a, &b);

if (a > min) min = a;

if (b < max) max = b;

}

Если min ≤ max, то выводим “YES”. Иначе выводим “NO”.

if (min <= max) puts("YES"); else puts("NO");

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int n = con.nextInt();

int min = 0, max = 32;

for(int i = 0; i < n; i++)

{

int a = con.nextInt();

int b = con.nextInt();

if (a > min) min = a;

if (b < max) max = b;

}

if (min <= max)

System.out.println("YES");

else

System.out.println("NO");

}

con.close();

}

}